The following relates to the data processing, compression, transfer, and related arts. It finds particular application in the acquisition, compression, and storage of images during printing, facsimile transfer, and related tasks, and is described with particular reference thereto. The following finds more general application in the storage or transfer of compressed data generally, such as for applications including document scanning, electronic database development, synchronization between computers or between a computer and a personal data assistant (PDA), and so forth.
Document scanning is prevalent in office environments, and is used in operations such as photocopying, scan-to-electronic file operations, facsimile transmissions, and so forth. Some office systems are multi-function devices (MFD's) that typically provide at least scanning, facsimile, photocopying, and printing functionality. These devices are typically operatively connected with a digital data network, such as a local area network (LAN) or wireless local area network (WLAN). The MFD receives input from an image input device such as a scanner bed, a multiple-sheet automated scanner (typically utilizing the scanner bed), or so forth. Alternatively, the digital data network may serve as the image input device, as the document to be printed, sent by facsimile, or otherwise published is received from the digital data network in a page description language (PDL) such as portable document format (PDF), PostScript, Scalable Vector Graphics (SVG), or so forth. A given MFD may be compatible with some PDL formats but not other PDL formats.
The received document is converted into a bitmap. A document received at the scanner bed is converted using an optical reader such as a charge-coupled device (CCD) array along with suitable electronics. A document received in PDL format is processed by suitable algorithms such as raster image processing (RIP) to generate bitmapped pages. To save memory, the image is compressed prior to storage, sometimes using dedicated compression electronics such as an application-specific integrated circuit (ASIC). The image is retrieved from memory at a later time, decompressed, optionally further processed, and ultimately output to a suitable output device such as a marking engine, facsimile engine, or so forth.
To facilitate extensive reading and writing of imaging data from and to electronic data storage, it is known to employ a direct memory access (DMA) engine to transfer imaging data to and from electronic memory autonomously with limited involvement of the central processing unit (CPU) of the MFD, printer, photocopier, or other device. In a typical approach, the DMA performs imaging data transfers while the CPU concurrently performs other tasks, such as image manipulation (e.g., resizing, rotation, format conversion, or so forth), control of the CCD acquisition array, control of the marking engine, or so forth. The DMA engine transmits interrupts to the CPU to coordinate operations of the DMA engine and the CPU. Receipt of an interrupt from the DMA engine causes the CPU to temporarily stop its current processing and handle the interrupt request, which may for example involve allocating a new memory block, identifying the new memory block allocation to the DMA engine, and requesting a new DMA transfer operation.
To minimize the interruptions of the CPU, it is known to use DMA chaining (also called “scatter/gather”) to transfer images to and from memory. In DMA chaining, the DMA engine performs autonomous transfer of multiple blocks of data without intervention of the CPU. For example, when an image spanning numerous memory blocks is to be read from memory, the image size (and hence the number of memory blocks) is known a priori. Accordingly, the CPU can request a DMA transfer of the entire set of memory blocks, and the DMA engine employs DMA chaining executing on the DMA engine to recall the entire image from memory in a single autonomous operation.
A problem arises, however, in that DMA chaining is difficult to apply to the compression and storage of images in memory. The image compression produces a widely varying and generally unpredictable image size. For example, the size of the compressed image can vary by a factor of ten or more depending upon the uncompressed image size, the compression algorithm used, parameters of the compression algorithm, the nature of the image (e.g., an image with lots of white space tends to compress much more efficiently than an image of higher complexity), the type of image (e.g., color, grayscale, halftone, etc.), and other factors. The compressed image size is not known a priori because it is compressed and stored “on the fly” with earlier-compressed portions of the image being stored while other portions of the image are still being compressed. Accordingly, it is difficult to use DMA chaining to efficiently load the compressed image into memory.
To address this problem, a common approach is to use a transfer block size that is expected to be typical for typical images processed by the MFD. This approach is less than optimal. If the typical transfer block size is substantially larger than the size of a particular image, then the result is inefficient use of memory as the substantially larger typical transfer block size is allocated for the substantially smaller image. Conversely, if the typical block size is substantially smaller than the size of a particular image, then processing is inefficient as numerous DMA transfer operations and correspondingly numerous CPU interrupts are required to transfer the substantially larger image to memory.